#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;

class Solution {
    struct Compare {
        bool operator()(const vector<int>& left, const vector<int>& right) {
            return left[1] > right[1];
        }
    };

public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<vector<int>>>graph(n);
        for (auto& flight : flights) 
            graph[flight[0]].push_back({ flight[1],flight[2] });
        //next,cost,k
        priority_queue<vector<int>, vector<vector<int>>, Compare> queue;
        queue.push({ src,0,K });
        while(!queue.empty()){
            auto node = queue.top();
            queue.pop();
            if (node[0] == dst)
                return node[1];
            if (node[2] == 0)
                continue;
            for (auto& next : graph[node[0]]) {
                queue.push({ next[0],next[1] + node[1],node[2] - 1 });
            }
        }

        return -1;
    }
};